package 面试题38_字符串的排列;

import java.lang.reflect.Array;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 12:28 2021/3/15
 * @Description：
 */
public class Solution {

    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        if (s == null) return new String[0];

        c = s.toCharArray();

        fix(0);

        String[] result = new String[res.size()];

        int i = 0;
        for (String ss: res) {
            result[i] = ss;
            i++;
        }

        return result;
    }

    void fix(int index) {
        // 递归结束条件，固定到最后一位
        if (index == c.length - 1) {
            res.add(String.valueOf(c));

            return;
        }
        HashSet<Character> set = new HashSet<>();// 用于判断当前位是否已经使用过某字符

        for (int i = index; i < c.length; i++) {
            if (set.contains(c[i])) continue;
            set.add(c[i]);

            swap(i, index);
            fix(index + 1);

            swap(i, index); // 复位，从而不影响其他分支
        }
    }

    void swap(int i, int j) {
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }
}
